package tree.递归;

import po.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 翻转二叉树以匹配先序遍历971.java
 * @Description https://leetcode-cn.com/problems/flip-binary-tree-to-match-preorder-traversal/
 * @createTime 2021年08月11日 19:23:00
 */
public class 翻转二叉树以匹配先序遍历971 {
	List<Integer> list = new ArrayList<>();
	int length = 0, index = 0;
	int[] array;

	public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
		length = voyage.length;
		array = voyage;
		dfs(root);
		//处理结果
		if (!list.isEmpty() && list.get(0)==-1){
			list.clear();
			list.add(-1);
		}
		return list;
	}

	private void dfs(TreeNode root) {
		/**
		 * 用前序遍历的方式来进行
		 */

		if (root == null) {
			return;
		}
		if (root.val != array[index]) {
			index += 1;
			list.clear();
			list.add(-1);
			return;
		}
		//index +1
		index+=1;
		//还没有遍历完，并且左节点不为空，还不等于下一个index
		if (index < length && root.left != null && root.left.val != array[index]) {
			list.add(root.val);
			//先遍历右子树，就相当于反转了左右子树
			dfs(root.right);
			dfs(root.left);
		} else {
			dfs(root.left);
			dfs(root.right);
		}
	}

}
